package pers.whj.util.list;

import pers.whj.util.InvalidParamException;
import pers.whj.util.NoSuchElementException;
import pers.whj.util.sort.Sort;

import java.lang.reflect.Array;

public class SeqList<T> implements List<T>, ListOp<T> {
    private static final int DEFAULT_SIZE = 16;

    protected Object[] mData;
    protected int mLength;
    private int mMaxLength;
    private boolean mCanResize;

    public SeqList() {
        this(DEFAULT_SIZE);
    }

    public SeqList(int maxLength) {
        this(maxLength, true);
    }

    public SeqList(int maxLength, boolean canResize) {
        mMaxLength = maxLength > 0 ? maxLength : DEFAULT_SIZE;
        mLength = 0;
        mData = new Object[mMaxLength];
        mCanResize = canResize;
    }

    @Override
    public int length() {
        return mLength;
    }

    public int getMaxLength() {
        return mMaxLength;
    }

    @Override
    public boolean contains(Object data) {
        return find(data) >= 0;
    }

    @Override
    public int find(Object data) {
        if (data == null) {
            for (int i = 0; i < mLength; i++) {
                if (mData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < mLength; i++) {
                if (data.equals(mData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public int findFromLast(Object data) {
        if (data == null) {
            for (int i = mLength - 1; i >= 0; i--) {
                if (mData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = mLength - 1; i >= 0; i--) {
                if (data.equals(mData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public int find(Object data, int start, int end) {
        checkIndexOfRange(start, end);
        if (data == null) {
            for (int i = start; i <= end; i++) {
                if (mData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i <= end; i++) {
                if (data.equals(mData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public int count(Object data) {
        int counts = 0;
        if (data == null) {
            for (int i = 0; i < mLength; i++) {
                if (mData[i] == null) {
                    counts++;
                }
            }
        } else {
            for (int i = 0; i < mLength; i++) {
                if (data.equals(mData[i])) {
                    counts++;
                }
            }
        }
        return counts;
    }

    @Override
    public T get(int index) {
        checkIndex(index);
        return data(index);
    }

    @Override
    public T getHead() {
        checkIfElementExists(0);
        return data(0);
    }

    @Override
    public T getTail() {
        checkIfElementExists(mLength - 1);
        return data(mLength - 1);
    }

    @Override
    public T set(int index, T data) {
        checkIndex(index);
        T oldData = data(index);
        mData[index] = data;
        return oldData;
    }

    @Override
    public T setHead(T data) {
        checkIfElementExists(0);
        T oldData = data(0);
        mData[0] = data;
        return oldData;
    }

    @Override
    public T setTail(T data) {
        int index = mLength - 1;
        checkIfElementExists(index);
        T oldData = data(index);
        mData[index] = data;
        return oldData;
    }

    @Override
    public void setAll(T data) {
        for (int i = 0; i < mLength; i++) {
            mData[i] = data;
        }
    }

    @Override
    public boolean insert(T data) {
        if (mLength < mMaxLength || expand()) {
            mData[mLength++] = data;
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(int index, T data) {
        checkIndexForInsert(index);
        if (mLength < mMaxLength || expand()) {
            System.arraycopy(mData, index, mData, index + 1, mLength - index);
            mData[index] = data;
            mLength++;
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(int index, T[] data) {
        checkIndexForInsert(index);
        int len = data == null ? 0 : data.length;
        if (len == 0) {
            return true;
        }
        int targetLen = mLength + len;
        if (targetLen <= mMaxLength || mCanResize) {
            if (targetLen > mMaxLength) {
                resize(targetLen, false);
            }
            System.arraycopy(mData, index, mData, index + len, mLength - index);
            System.arraycopy(data, 0, mData, index, len);
            mLength += len;
            return true;
        }
        return false;
    }

    @Override
    public boolean insertHead(T data) {
        return insert(0, data);
    }

    @Override
    public boolean insertTail(T data) {
        return insert(mLength, data);
    }

    @Override
    public T delete() {
        checkIndex(mLength - 1);
        T oldData = data(--mLength);
        mData[mLength] = null;
        return oldData;
    }

    @Override
    public T delete(int index) {
        checkIndex(index);
        int counts = mLength - index - 1;
        if (counts > 0) {
            System.arraycopy(mData, index + 1, mData, index, counts);
        }
        T oldData = data(--mLength);
        mData[mLength] = null;
        return oldData;
    }

    @Override
    public void delete(int from, int end) {
        checkIndexOfRange(from, end);
        int counts = mLength - end - 1;
        if (counts > 0) {
            System.arraycopy(mData, end + 1, mData, from, counts);
        }
        for (int i = from + counts; i < mLength; i++) {
            mData[i] = null;
        }
        mLength = from + counts;
    }

    @Override
    public boolean delete(Object data) {
        int index = find(data);
        if (index == -1) {
            return false;
        }
        delete(index);
        return true;
    }

    @Override
    public boolean deleteFromLast(Object data) {
        int index = findFromLast(data);
        if (index == -1) {
            return false;
        }
        delete(index);
        return true;
    }

    @Override
    public int deleteAll(Object data) {
        int counts = 0;
        int left = 0, right = 0;
        if (data == null) {
            while (right < mLength) {
                if (mData[right] != null) {
                    mData[left++] = mData[right++];
                } else {
                    right++;
                    counts++;
                }
            }
        } else {
            while (right < mLength) {
                if (!data.equals(mData[right])) {
                    mData[left++] = mData[right++];
                } else {
                    right++;
                    counts++;
                }
            }
        }
        for (int i = left; i < mLength; i++) {
            mData[i] = null;
        }
        mLength = left;
        return counts;
    }

    @Override
    public T deleteHead() {
        checkIfElementExists(0);
        return delete(0);
    }

    @Override
    public T deleteTail() {
        checkIfElementExists(mLength - 1);
        T oldData = data(--mLength);
        mData[mLength] = null;
        return oldData;
    }

    @Override
    public boolean isEmpty() {
        return mLength == 0;
    }

    @Override
    public void clear() {
        if (mCanResize) {
            mData = new Object[DEFAULT_SIZE];
            mMaxLength = DEFAULT_SIZE;
        } else {
            for (int i = 0; i < mLength; i++) {
                mData[i] = null;
            }
        }
        mLength = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new SeqListIterator();
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[mLength];
        System.arraycopy(mData, 0, array, 0, mLength);
        return array;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T[] toArray(Class<T> type) {
        Object copy = Array.newInstance(type, mLength);
        System.arraycopy(mData, 0, copy, 0, mLength);
        return (T[]) copy;
    }

    @Override
    public boolean merge(List<T> list) {
        if (list != null) {
            if (list.length() == 0) {
                return true;
            }
            int targetLen = mLength + list.length();
            if (targetLen <= mMaxLength || mCanResize) {
                if (targetLen > mMaxLength) {
                    resize(targetLen, false);
                }
                System.arraycopy(list.toArray(), 0, mData, mLength, list.length());
                mLength += list.length();
                return true;
            }
        }
        return false;
    }

    @Override
    public SeqList<T> subList(int offset, int length) {
        checkLength(length);
        checkIndex(offset);
        SeqList<T> subList = new SeqList<>(length, mCanResize);
        if (length > 0) {
            checkIndex(offset + length - 1);
            System.arraycopy(mData, offset, subList.mData, 0, length);
            subList.mLength = length;
        }
        return subList;
    }

    @Override
    public SeqList<T> subList(int start, int end, int step) {
        checkIndexOfRange(start, end);
        if (step < 1) {
            step = 1;
        }
        if (step == 1) {
            return subList(start, end - start + 1);
        } else {
            SeqList<T> subList = new SeqList<>();
            for (int i = start; i <= end; i += step) {
                subList.insert(data(i));
            }
            subList.setCanResize(mCanResize);
            return subList;
        }
    }

    @Override
    public void reverse() {
        reverse(0, mLength - 1);
    }

    @Override
    public void reverse(int start, int end) {
        checkIndexOfRange(start, end);
        Object tmp;
        while (start < end) {
            tmp = mData[start];
            mData[start] = mData[end];
            mData[end] = tmp;
            start++;
            end--;
        }
    }

    @Override
    public void rotate(int k) {
        rotate(0, mLength - 1, k);
    }

    @Override
    public void rotate(int start, int end, int k) {
        if (k >= 0) {
            checkIndexOfRange(start, end);
            int length = end - start + 1;
            k = k % length;
            if (k > 0) {
                Object[] tmp = new Object[length];
                System.arraycopy(mData, start, tmp, 0, length);
                k = length - k - start;
                for (int i = start; i <= end; i++) {
                    mData[i] = tmp[(i + k) % length];
                }
            }
        }
    }

    @Override
    public void sort() {
        sort(0, mLength - 1);
    }

    @Override
    public void sort(int start, int end) {
        Sort.sort(mData, start, end);
    }

    @Override
    public void shuffle() {
        ListOp.shuffle(mData, 0, mLength - 1);
    }

    @Override
    public void shuffle(int start, int end) {
        checkIndexOfRange(start, end);
        ListOp.shuffle(mData, start, end);
    }

    public int binarySearch(Object data) {
        return binarySearch(data, 0, mLength - 1);
    }

    /**
     * find target data by binary search
     *
     * @param data  target data
     * @param start begin index
     * @param end   end index
     * @return the index of target data or -1 if does not find the data
     */
    @SuppressWarnings({"unchecked"})
    public int binarySearch(Object data, int start, int end) {
        checkIndexOfRange(start, end);
        Comparable<T> comparable = (Comparable<T>) data;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (comparable.compareTo(data(mid)) == 0) {
                return mid;
            } else if (comparable.compareTo(data(mid)) < 0) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public void resize(boolean expand) {
        if (mCanResize) {
            if (expand) {
                expand();
            } else {
                resize(Math.max(mLength, 1), false);
            }
        }
    }

    public void resize(int targetLength, boolean truncated) {
        if (mCanResize) {
            if (targetLength > mMaxLength) {
                mMaxLength = targetLength;
                copyArray(mMaxLength, mLength);
            } else if (targetLength < mMaxLength) {
                targetLength = Math.max(targetLength, 1);
                if (targetLength >= mLength || truncated) {
                    mMaxLength = targetLength;
                    mLength = Math.min(mLength, targetLength);
                    copyArray(mMaxLength, mLength);
                }
            }
        }
    }

    public void setCanResize(boolean canResize) {
        mCanResize = canResize;
    }

    public boolean canResize() {
        return mCanResize;
    }

    @SuppressWarnings("unchecked")
    protected T data(int index) {
        return (T) mData[index];
    }

    protected void checkIndex(int index) {
        if (index < 0 || index >= mLength) {
            throw new IndexOutOfBoundsException("index: " + index + ", length: " + mLength);
        }
    }

    protected void checkIndexForInsert(int index) {
        if (index < 0 || index > mLength) {
            throw new IndexOutOfBoundsException("index: " + index + ", length: " + mLength);
        }
    }

    protected void checkIndexOfRange(int from, int end) {
        checkIndex(from);
        checkIndex(end);
        if (from > end) {
            throw new IndexOutOfBoundsException("indexes of range are wrong: from: " + from + ", end: " + end);
        }
    }

    protected void checkLength(int length) {
        if (length < 0) {
            throw new InvalidParamException("length is negative: " + length);
        }
    }

    protected void checkIfElementExists(int index) {
        if (index < 0 || index >= mLength) {
            throw new NoSuchElementException("index: " + index + ", list length: " + mLength);
        }
    }

    protected void checkWhileInsert() {
        if (!mCanResize && mLength == mMaxLength) {
            throw new IllegalStateException("list is full, cannot insert any data");
        }
    }

    private boolean expand() {
        if (!mCanResize || mMaxLength == Integer.MAX_VALUE) {
            return false;
        }
        int delta = Math.max(mMaxLength >> 1, 1);
        if (mMaxLength > Integer.MAX_VALUE - delta) {
            mMaxLength = Integer.MAX_VALUE;
        } else {
            mMaxLength += delta;
        }
        copyArray(mMaxLength, mLength);
        return true;
    }

    private void copyArray(int newLength, int dataLength) {
        Object[] newData = new Object[newLength];
        dataLength = Math.min(dataLength, mLength);
        if (dataLength >= 0) {
            System.arraycopy(mData, 0, newData, 0, dataLength);
        }
        mData = newData;
    }

    private class SeqListIterator implements Iterator<T> {
        int cursor = 0;
        int lastReturn = -1;
        boolean forwardDir = true;

        @Override
        public boolean hasNext() {
            if (mLength <= 0) {
                return false;
            }
            return forwardDir ? cursor != mLength : cursor != -1;
        }

        @Override
        public T next() {
            if (cursor >= mLength || cursor < 0) {
                throw new NoSuchElementException("cursor: " + cursor + ", length: " + mLength);
            } else {
                int i = cursor;
                if (forwardDir) {
                    cursor++;
                } else {
                    cursor--;
                }
                lastReturn = i;
                return data(i);
            }
        }

        @Override
        public void remove() {
            if (lastReturn < 0) {
                throw new IllegalStateException("index of last return element is illegal");
            }
            SeqList.this.delete(lastReturn);
            if (forwardDir) {
                cursor--;
            }
            lastReturn = -1;
        }

        @Override
        public int index() {
            return cursor;
        }

        @Override
        public void reset() {
            cursor = forwardDir ? 0 : mLength - 1;
        }

        @Override
        public void setDirection(boolean reverse) {
            forwardDir = !reverse;
        }
    }
}